//剪枝法求第n个斐波那契数列的值
#include<iostream>
#include<unordered_map>
using namespace std;
class Solution
{
public:
	int Fibonacci(int n)
	{
		if (n == 0 || n == 1)
		{
			return n;
		}
		if (n == 2)
		{
			return 1;
		}
		//如果求第n个fibonacci,就需要先查找第n-1个是否存在
		//查找第n-1个 
		int pre = 0;
		if (filter.find(n - 1) == filter.end())
		{
			//end是最后一个元素之后的位置，[begin,end)
			//如果没有找到第n-1个，就计算，并且将结果插入到filter逻辑（内嵌递归）
			pre = Fibonacci(n - 1);
			//插入filter逻辑，下次就不用再重复计算了
			filter.insert({ n - 1,pre });
		}
		else
		{
			//如果找到了，就直接拿出来，下次不用再次重复计算
			pre = filter[n - 1];
		}
		//如果求第n个fibonacci, 就需要先查找第n - 1个是否存在，
		//而这里先求n-2,可以让n-1使用n-2计算的结果
		//查找第n-2个
		int ppre = 0;
		if (filter.find(n - 2) == filter.end())
		{
			//如果没有找到第n-2个，就计算，并且将结果插入到filter逻辑（内嵌递归）
			ppre = Fibonacci(n - 2);
			//插入filter逻辑，下次就不用再重复计算了
			filter.insert({ n - 2,ppre });
		}
		else
		{
			//如果找到了，就直接拿出来，下次不用再次重复计算
			ppre = filter[n - 2];
		}
		
		val = pre + ppre;
		return val;
	}
	void Print()const
	{
		cout << val << endl;
	}
private:
	unordered_map<int, int> filter;
	size_t val;
};
int main()
{
	Solution fib;
	fib.Fibonacci(45);
	fib.Print();
    return 0;
}
